package suanfa.linklist.第一章第一节;

import suanfa.linklist.Node;

public class Test2 {

    public static void reverse(Node head){
        //判断链表是否为空
        if(head==null || head.next==null){
            return;
        }

        Node cur=null;//当前节点
        Node next=null;//后继节点

        //设置链表的第一个节点为尾结点
        cur=head.next.next;//1234567

        head.next.next=null;

        //把遍历到节点插入到头结点的后面
        while(cur!=null){
            //这个就是个临时变量，获取剩下的元素，每次减少一个
            Node tmp=cur.next;//next:234567   cur:1234567 head:00
//这一行跟下面一行很关键，一起改变了head的值，这行理解不了
            cur.next=head.next;//经过这一行：cur变化：1234567 -->10
//这一行很关键，是在这里把head的值改了，一步一步从正序变成了倒序。
//            有点领悟了，这行就是书中说的插入法的：把当前遍历到的节点插入到头结点后面
            head.next=cur;//经过这一行，head变化：00---->10

            cur=tmp;//cur变化：10 --->234567  head:010
        }



    }


    public static void main(String[] args) {
        Node head = new Node();

        head.next = null;

        Node tmp;
        Node cur = head;

        //构造单链表，这个也理解怎么实现的
        for (int i = 0; i < 8; i++) {

            //这个必须放到外面定义，for循环里每次都new一个，链表的next永远是null，不对，放外面也一样
            //Node tmp=new Node();
            tmp = new Node();

            //这两行是为了构建最新的节点，即最后的节点
            tmp.data = i;
            tmp.next = null;

            cur.next = tmp;//这一行很关键，走完这一行，head的值就变了。但为什么cur变了，head也会跟着变？

            cur = tmp;//这里是为了让cur等于最后一个节点的值

        }

        System.out.print("逆序前：");
        for (cur = head.next; cur != null; cur = cur.next) {
            //注意这里不是println
            System.out.print(cur.data + " ");
        }


        System.out.print("逆序后：");

        reverse(head);

        for (Node cur1 = head.next; cur1 != null; cur1 = cur1.next) {
            //注意这里不是println
            System.out.print(cur1.data + " ");
        }
    }
}
